package hard;

import java.util.Arrays;

/**
 * 给定一个正整数、负整数和 0 组成的 N × M矩阵，编写代码找出元素总和最大的子矩阵。
 *
 * 返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，
 * r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。
 *
 * 链接：https://leetcode.cn/problems/max-submatrix-lcci
 * @author 胡宇轩
 * @Email: programboy@163.com
 */
public class MaxSubmatrixLcci {
    /**
     * hard级别，没有官方解答。看了一下网友的解答，能看明白大致的思路，但是一些细节不太懂。
     * 后面按照提供的代码，自己在纸上去画过程，这才明白了作者的良苦用心。
     *
     * 前缀和 + 动态规划
     * */
    class Solution {
        public int[] getMaxMatrix(int[][] matrix) {
            int matrixRows = matrix.length;
            int matrixCols = matrix[0].length;
            int[] ans = new int[4];
            // 用于记录列的前缀和
            int[] b = new int[matrix[0].length];
            int sum = 0;
            int maximum = Integer.MIN_VALUE;
            int rs = 0;
            int cs = 0;

            for (int i = 0; i < matrixRows; i++) {
                // 每次更改起始行后，b数组就要清零
                for (int j = 0; j < matrixCols; j++) {
                    b[j] = 0;
                }
                for (int j = i; j < matrixRows; j++) {
                    sum = 0;
                    for (int k = 0; k < matrixCols; k++) {
                        b[k] += matrix[j][k];

                        if (sum > 0) {
                            sum += b[k];
                        } else {
                            sum = b[k];
                            // 记录开始坐标 rs表示开始的行，cs表示开始的列
                            // rs为啥是i行开始？ 因为我们现在就是从i行开始累加到j行的，自然记录起始行
                            rs = i;
                            cs = k;
                        }

                        if (sum > maximum) {
                            maximum = sum;
                            ans[0] = rs;
                            ans[1] = cs;
                            ans[2] = j;
                            ans[3] = k;
                        }
                    }
                }
            }
            return ans;
        }
    }
}
